#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

//1:用队列实现栈
/*方法1：入栈操作时，首先获得入栈前的元素个数 nnn，然后将元素入队到队列，
再将队列中的前 nnn 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，
此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。
*/
/*
实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
*/
typedef int QDateType;
typedef struct QNode
{
    QDateType date;
    struct QNode* next;
}QNode;


typedef struct {
    QNode* head;
    QNode* tail;
    int size;
} MyStack;



MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    stack->head = stack->tail = NULL;
    stack->size = 0;
    return stack;
}


int myStackPop(MyStack* obj) {
    //头删
    int tmp = obj->head->date;
    if (obj->head->next == NULL)
    {
        free(obj->head);
        obj->head = obj->tail = NULL;
    }
    else
    {
        QNode* next = obj->head->next;
        free(obj->head);
        obj->head = next;
    }
    obj->size--;
    return tmp;
}


void QueuePush(MyStack* obj, int x)
{
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    newnode->date = x;
    newnode->next = NULL;
    if (obj->size == 0)
    {
        obj->head = obj->tail = newnode;
    }
    else
    {
        obj->tail->next = newnode;
        obj->tail = newnode;
    }
    obj->size++;
}


void myStackPush(MyStack* obj, int x) {
    int n = obj->size;
    QueuePush(obj, x);
    while (n--)
    {
        QueuePush(obj, myStackPop(obj));
    }


}



int myStackTop(MyStack* obj) {
    return obj->head->date;
}


bool myStackEmpty(MyStack* obj) {
    if (obj->size == 0)
        return true;
    else
        return false;
}


void myStackFree(MyStack* obj) {
    while (obj->size > 0)
    {
        myStackPop(obj);
    }
}


//2:用栈实现队列
/*
将一个栈当作输入栈，用于压入 push\texttt{push}push 传入的数据；
另一个栈当作输出栈，用于 pop\texttt{pop}pop 和 peek\texttt{peek}peek 操作。

每次 pop\texttt{pop}pop 或 peek\texttt{peek}peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，
这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
*/
/*
实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
*/
#define InitCapacity 10
typedef int SDatrType;
typedef struct Stack
{
    SDatrType* p;
    int top;
    int capacity;
}Stack;

typedef struct {
    Stack stk_push;
    Stack stk_pop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* stack = (MyQueue*)malloc(sizeof(MyQueue));
    stack->stk_push.p = (SDatrType*)malloc(InitCapacity * sizeof(SDatrType));
    stack->stk_pop.p = (SDatrType*)malloc(InitCapacity * sizeof(SDatrType));
    stack->stk_push.top = stack->stk_pop.top = -1;
    stack->stk_push.capacity = stack->stk_pop.capacity = InitCapacity;
    return stack;
}

void AddMemory(Stack* s)
{
    if (s->top + 1 == s->capacity)
    {
        int newcapacity = 2 * (s->capacity);
        s->p = (SDatrType*)realloc(s->p, newcapacity * sizeof(SDatrType));
        s->capacity = newcapacity;
    }
}

//入队
void myQueuePush(MyQueue* obj, int x) {
    AddMemory(&(obj->stk_push));
    obj->stk_push.p[obj->stk_push.top + 1] = x;
    obj->stk_push.top += 1;

}

int StackPop(Stack* s)
{
    int tmp = s->p[s->top];
    s->top--;
    return tmp;
}

//出队
int myQueuePop(MyQueue* obj) {
    if (obj->stk_pop.top + 1 == 0)
    {
        int n = obj->stk_push.top + 1;
        while (n--)
        {
            AddMemory(&(obj->stk_pop));
            obj->stk_pop.p[obj->stk_pop.top + 1] = StackPop(&(obj->stk_push));
            obj->stk_pop.top += 1;
        }
    }
    return StackPop(&(obj->stk_pop));
}

//获取队头元素
int myQueuePeek(MyQueue* obj) {
    int i = myQueuePop(obj);
    obj->stk_pop.top++;
    return i;
}

bool myQueueEmpty(MyQueue* obj) {
    if (obj->stk_push.top + 1 == 0 && obj->stk_pop.top + 1 == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//销毁
void myQueueFree(MyQueue* obj) {
    free(obj->stk_push.p);
    obj->stk_push.p = NULL;
    free(obj->stk_pop.p);
    obj->stk_pop.p = NULL;
    obj->stk_push.top = obj->stk_pop.top = -1;
    obj->stk_push.capacity = obj->stk_pop.capacity = 0;
    free(obj);
}



//3:设计实现循环队列(数组)
/*设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
*/

typedef struct {
    int* p;
    int front;
    int tear;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* CircularQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CircularQueue->p = (int*)malloc((k + 1) * sizeof(int));
    CircularQueue->front = CircularQueue->tear = 0;
    CircularQueue->k = k;
    return CircularQueue;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tear + 1) % (obj->k + 1) == obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->p[obj->tear] = value;
        obj->tear = (obj->tear + 1) % (obj->k + 1);
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else {
        obj->front = (obj->front + 1) % (obj->k + 1);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->p[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->p[(obj->tear + obj->k) % (obj->k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->p);
    obj->p = NULL;
    free(obj);
}
